package com.gxgeek.algorithm.t2;

import java.util.Scanner;

/**
 * Created by gx on 2017/5/8.
 */
public class Tree {
}

class CBTType                //定义二叉树结点类型
{
    String data;                //元素数据
    CBTType left;                //左子树结点指针
    CBTType right;            //右子树结点指针
}


class P2_5 {
    static final int MAXLEN = 20;
    static Scanner input = new Scanner(System.in);

    CBTType InitTree()                        //初始化二叉树的根
    {
        CBTType node;

        if ((node = new CBTType()) != null) //申请内存
        {
            System.out.printf("请先输入一个根结点数据:\n");
            node.data = input.next();
            node.left = null;
            node.right = null;
//			if(node!=null) 					//如果二叉树根结点不为空
//			{
            return node;
//			}
//			else
//			{
//				return null;
//			}
        }
        return null;
    }

    void AddTreeNode(CBTType treeNode)            //添加结点
    {
        CBTType pnode, parent;
        String data;
        int menusel;

        if ((pnode = new CBTType()) != null) //分配内存
        {
            System.out.printf("输入二叉树结点数据:\n");

            pnode.data = input.next();
            pnode.left = null;                    //设置左右子树为空
            pnode.right = null;

            System.out.printf("输入该结点的父结点数据:");
            data = input.next();

            parent = TreeFindNode(treeNode, data);    //查找指定数据的结点
            if (parent == null)                            //如果未找到
            {
                System.out.printf("未找到该父结点!\n");
                pnode = null;                    //释放创建的结点内存
                return;
            }
            System.out.printf("1.添加该结点到左子树\n2.添加该结点到右子树\n");
            do {
                menusel = input.nextInt();                    //输入选择项

                if (menusel == 1 || menusel == 2) {
                    if (parent == null) {
                        System.out.printf("不存在父结点，请先设置父结点!\n");
                    } else {
                        switch (menusel) {
                            case 1:            //添加到左结点
                                if (parent.left != null)    //左子树不为空
                                {
                                    System.out.printf("左子树结点不为空!\n");
                                } else {
                                    parent.left = pnode;
                                }
                                break;
                            case 2:            //添加到右结点
                                if (parent.right != null) //右子树不为空
                                {
                                    System.out.printf("右子树结点不为空!\n");
                                } else {
                                    parent.right = pnode;
                                }
                                break;
                            default:
                                System.out.printf("无效参数!\n");
                        }
                    }
                }
            } while (menusel != 1 && menusel != 2);
        }
    }

    CBTType TreeFindNode(CBTType treeNode, String data)    //查找结点
    {
        CBTType ptr;

        if (treeNode == null) {
            return null;
        } else {
            if (treeNode.data.equals(data)) {
                return treeNode;
            } else {                                        // 分别向左右子树递归查找
                if ((ptr = TreeFindNode(treeNode.left, data)) != null) {
                    return ptr;
                } else if ((ptr = TreeFindNode(treeNode.right, data)) != null) {
                    return ptr;
                } else {
                    return null;
                }
            }
        }
    }

    CBTType TreeLeftNode(CBTType treeNode)    //获取左子树
    {
        if (treeNode != null) {
            return treeNode.left;                    //返回值
        } else {
            return null;
        }
    }

    CBTType TreeRightNode(CBTType treeNode)    //获取右子树
    {
        if (treeNode != null) {
            return treeNode.right;                //返回值
        } else {
            return null;
        }
    }

    int TreeIsEmpty(CBTType treeNode)            //判断空树
    {
        if (treeNode != null) {
            return 0;
        } else {
            return 1;
        }
    }

    int TreeDepth(CBTType treeNode)                //计算二叉树深度
    {
        int depleft, depright;

        if (treeNode == null) {
            return 0; //对于空树，深度为0
        } else {
            depleft = TreeDepth(treeNode.left);        //左子树深度 (递归调用)
            depright = TreeDepth(treeNode.right);    //右子树深度 (递归调用)
            if (depleft > depright) {
                return depleft + 1;
            } else {
                return depright + 1;
            }
        }
    }

    void ClearTree(CBTType treeNode)        // 清空二叉树
    {
        if (treeNode != null) {
            ClearTree(treeNode.left);        //清空左子树
            ClearTree(treeNode.right);        //清空右子树
            treeNode = null;                    //释放当前结点所占内存
//	         treeNode=null;
        }
    }

    void TreeNodeData(CBTType p)            //显示结点数据
    {
        System.out.printf("%s ", p.data);                //输出结点数据
    }


    void LevelTree(CBTType treeNode){    //按层遍历

        CBTType p;
        CBTType[] q = new CBTType[MAXLEN];                                        //定义一个顺序栈
        int head = 0, tail = 0;

        if (treeNode != null) {                                              //如果队首指针不为空
            tail = (tail + 1) % MAXLEN;                                    //计算循环队列队尾序号
            q[tail] = treeNode;                                        //将二叉树根指针进队
        }
        while (head != tail) {                                           //队列不为空，进行循环
            head = (head + 1) % MAXLEN;                                //计算循环队列的队首序号
            p = q[head];                                            //获取队首元素
            TreeNodeData(p);                                        //处理队首元素
            if (p.left != null) {                                       //如果结点存在左子树
                tail = (tail + 1) % MAXLEN;                                //计算循环队列的队尾序号
                q[tail] = p.left;                                        //将左子树指针进队
            }

            if (p.right != null){                                        //如果结点存在右子树
                tail = (tail + 1) % MAXLEN;                                //计算循环队列的队尾序号
                q[tail] = p.right;                                        //将右子树指针进队
            }
        }
    }


    void DLRTree(CBTType treeNode)  //先序遍历
    {
        if (treeNode != null) {
            TreeNodeData(treeNode);  //显示结点的数据(当前节点数据
            DLRTree(treeNode.left);
            DLRTree(treeNode.right);
        }
    }

    void LDRTree(CBTType treeNode)  //中序遍历
    {
        if (treeNode != null) {
            LDRTree(treeNode.left);                    //中序遍历左子树
            TreeNodeData(treeNode);                                //显示结点数据
            LDRTree(treeNode.right);                //中序遍历右子树
        }
    }

    void LRDTree(CBTType treeNode) //后序遍历
    {
        if (treeNode != null) {
            LRDTree(treeNode.left);                    //后序遍历左子树
            LRDTree(treeNode.right);                //后序遍历右子树
            TreeNodeData(treeNode);                                //显示结点数据
        }
    }

    public static void main(String[] args) {
        CBTType root = null;        //root为指向二叉树根结点的指针
        int menusel;
        P2_5 t = new P2_5();
        //设置根元素
        root = t.InitTree();
        //添加结点
        do {
            System.out.printf("请选择菜单添加二叉树的结点\n");
            System.out.printf("0.退出\t");            //显示菜单
            System.out.printf("1.添加二叉树的结点\n");
            menusel = input.nextInt();
            switch (menusel) {
                case 1:            //添加结点
                    t.AddTreeNode(root);
                    break;
                case 0:
                    break;
                default:
                    ;
            }
        } while (menusel != 0);

        //遍历
        do {
            System.out.printf("请选择菜单遍历二叉树,输入0表示退出:\n");
            System.out.printf("1.先序遍历DLR\t");    //显示菜单
            System.out.printf("2.中序遍历LDR\n");
            System.out.printf("3.后序遍历LRD\t");
            System.out.printf("4.按层遍历\n");
            menusel = input.nextInt();
            switch (menusel) {
                case 0:
                    break;
                case 1:                //先序遍历
                    System.out.printf("\n先序遍历DLR的结果：");
                    t.DLRTree(root);
                    System.out.printf("\n");
                    break;
                case 2:                //中序遍历
                    System.out.printf("\n中序LDR遍历的结果：");
                    t.LDRTree(root);
                    System.out.printf("\n");
                    break;
                case 3:                //后序遍历
                    System.out.printf("\n后序遍历LRD的结果：");
                    t.LRDTree(root);
                    System.out.printf("\n");
                    break;
                case 4:                //按层遍历
                    System.out.printf("\n按层遍历的结果：");
                    t.LevelTree(root);
                    System.out.printf("\n");
                    break;
                default:
                    ;
            }
        } while (menusel != 0);
        //深度
        System.out.printf("\n二叉树深度为:%d\n", t.TreeDepth(root));

        t.ClearTree(root);            //清空二叉树
        root = null;


    }

}
